package Leetcode.sliding_window;

import java.util.Arrays;

/**
 * @Author: kirito
 * @Date: 2024/3/26 15:00
 * @Description:
 * 大小为 K 且平均值大于等于阈值的子数组数目
 * 给你一个整数数组 arr 和两个整数 k 和 threshold 。
 *
 * 请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。
 *
 *
 *
 * 示例 1：
 *
 * 输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
 * 输出：3
 * 解释：子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 4，5 和 6 。其他长度为 3 的子数组的平均值都小于 4 （threshold 的值)。
 * 示例 2：
 *
 * 输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
 * 输出：6
 * 解释：前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。
 *
 *
 * 提示：
 *
 * 1 <= arr.length <= 105
 * 1 <= arr[i] <= 104
 * 1 <= k <= arr.length
 * 0 <= threshold <= 104
 */

public class numOfSubarrays {
    public static void main(String[] args) {
        int[] arr = {11, 13, 17, 23, 29, 31, 7, 5, 2, 3};
        int k = 3;
        int th = 5;
        System.out.println(numOfSubarrays(arr, k, th));
    }

    /**
     * 子数组最少包含一个元素，它是原数组中的一个连续序列。与子数组相对的是子序列，子序列可以在原序列中不连续
     *连续序列--连续序列--连续序列--连续序列
     * 思路题目跟之前那个minimumDifference有点像
     * 1.先排序，然后k为窗口单位计算平均值，每次移动涉及到中间单位的重复计算，所以只对首尾进行计算优化性能
     * 连续序列--连续序列--连续序列--连续序列
     * 所以不能排序
     * @param arr
     * @param k
     * @param threshold
     * @return
     */
    public static int numOfSubarrays(int[] arr, int k, int threshold) {
        int temp = 0;
        int target = k * threshold;
        int sum = 0;
        //为什么排序了他就是7了啊？？？？
        //连续序列--连续序列--连续序列--连续序列 不能排序
//        Arrays.sort(arr);
        for (int i = 0; i < k; i++) {
            sum += arr[i];
        }

        if (sum >= target) {
            temp++;
        }

        for (int i = k; i < arr.length; i++) {
            sum += arr[i] - arr[i - k];
            if (sum >= target) {
                temp++;
            }
        }

        return temp;
    }
}
